// 提交链接 https://leetcode.cn/problems/house-robber/submissions/530590288/
// 198. 打家劫舍
// 完成日期： 2024.9.8
// c++ 动态规划枚举打劫的房子

class Solution {
public:
    pair<int, int> dp[105];
    int rob(vector<int>& nums) {
        return dfs(nums.size() - 1, nums);
    }
    int dfs(int i, vector<int>& nums)
    {
        if (i < 0) return 0;
        if (dp[i].first) return dp[i].second;
        int ans = dfs(i - 1, nums);
        ans = max(ans, dfs(i - 2, nums) + nums[i]);
        dp[i].first = 1;
        return dp[i].second = ans;
    }
};